package g

import (
	"fmt"
	"sort"
)

/*
 * @lc app=leetcode.cn id=18 lang=golang
 *
 * [18] 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。
请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]
（若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
*/

// @lc code=start
func fourSum(nums []int, target int) [][]int {
	// return fourSum1(nums, target) // out of memory
	// return fourSum2(nums, target) // 272ms
	return fourSum3(nums, target) // 16ms
}

func fourSum1(nums []int, target int) [][]int {
	sort.Ints(nums)
	var results [][]int
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			for k := j + 1; k < len(nums); k++ {
				for l := k + 1; l < len(nums); l++ {
					if nums[i]+nums[j]+nums[k]+nums[l] == target {
						results = append(results, []int{nums[i], nums[j], nums[k], nums[l]})
					}
				}
			}
		}
	}
	results = rmDup(results)
	return results
}

func rmDup(vals [][]int) [][]int {
	var result [][]int
	uniqueVal := make(map[string]bool)
	for _, val := range vals {
		tmp := fmt.Sprintf("%v_%v_%v_%v", val[0], val[1], val[2], val[3])
		if !uniqueVal[tmp] {
			uniqueVal[tmp] = true
			result = append(result, val)
		}
	}
	return result
}

func fourSum2(nums []int, target int) [][]int {
	sort.Ints(nums)
	var results [][]int
	for i := 0; i < len(nums)-3; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		for j := i + 1; j < len(nums)-2; j++ {
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}
			for k := j + 1; k < len(nums)-1; k++ {
				if k > j+1 && nums[k] == nums[k-1] {
					continue
				}
				for l := k + 1; l < len(nums); l++ {
					if l > k+1 && nums[l] == nums[l-1] {
						continue
					}
					if nums[i]+nums[j]+nums[k]+nums[l] == target {
						results = append(results, []int{nums[i], nums[j], nums[k], nums[l]})
					}
				}
			}
		}
	}
	return results
}

// fourSum3 参考3个数求和，时间复杂度o(n^3)
func fourSum3(nums []int, target int) [][]int {
	sort.Ints(nums)
	var results [][]int
	for i := 0; i < len(nums)-3; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		for j := i + 1; j < len(nums)-2; j++ {
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}
			l := len(nums) - 1
			for k := j + 1; k < l; k++ {
				if k > j+1 && nums[k] == nums[k-1] {
					continue
				}
				for ; l > k; l-- {
					if l < len(nums)-1 && nums[l] == nums[l+1] {
						continue
					}
					if nums[i]+nums[j]+nums[k]+nums[l] <= target {
						break
					}
				}
				if k == l {
					break
				}
				if nums[i]+nums[j]+nums[k]+nums[l] == target {
					results = append(results, []int{nums[i], nums[j], nums[k], nums[l]})
				}
			}
		}
	}
	return results
}

// @lc code=end
